package Leetcode第一期;

import java.util.Arrays;

/**
 * @author : K k
 * @date : 11:37 2020/9/16
 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
 *
 *  
 *
 * 示例：
 *
 * 输入：nums = [-1,2,1,-4], target = 1
 * 输出：2
 * 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
 */
public class 最接近的三数之和_16 {

    //双指针
    public int threeSumClosest(int[] nums, int target) {
        int tmp=Integer.MAX_VALUE;
        int ans=0;
        Arrays.sort(nums);//从小到大排序
        if (nums.length<3||nums==null) return ans;
        int len=nums.length;

        for (int i=0;i<len;i++){
            int left=i+1;
            int right=len-1;
            while (left<right){
                int sum=nums[i]+nums[left]+nums[right];
                int temp=tmp;
                tmp=Math.min(tmp,Math.abs(sum-target));
                if(temp!=tmp){
                    ans=sum;
                }

                if(sum<target)left++;
                else if (sum>target)right--;
                else if(sum==target) break;
            }
        }
        return ans;
    }

    //双指针
    public int threeSumClosestA(int[] nums,int target){
        Arrays.sort(nums);
        int result = nums[0] + nums[1] + nums[2];
        for(int i=0;i<nums.length-2;i++){
            int left = i+1;
            int right = nums.length - 1;
            while(left != right){
                int sum = nums[i] + nums[left] + nums[right];
                if(Math.abs(sum - target) < Math.abs(result - target))
                    result = sum;
                if(sum > target){
                    right--;
                    // 解决nums[right]重复
                    while(left != right && nums[right] == nums[right+1])
                        right--;
                }
                else{
                    left++;
                    // 解决nums[left]重复
                    while(left != right && nums[left] == nums[left-1])
                        left++;
                }
            }
            // 解决nums[i]重复
            while(i<nums.length-2 && nums[i] == nums[i+1])
                i++;
        }
        return result;
    }
}
